#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;



template <class T>
class UnionFindSet
{
public:
    //构造函数
    UnionFindSet() {}
    //插入元素接口
    bool insert(T t)
    {
        auto it = mp.find(t);
        if (it != mp.end())
        {
            return false;
        }
        int size = _fa.size();
        mp[t] = size;
        mpt[size] = t;
        _fa.push_back(-1);
    }

    //查找所属集合
    int Findroot(T t)
    {
        auto it = mp.find(t);
        if (it == mp.end())
        {
            return -1;
        }
        int x = mp[t];  //找到需要查找元素的下标
        int father = _fa[x];    //找到节点
        if (father < 0)
        {
            return x;
        }
        string fs = mpt[father];
        return _fa[x] = Findroot(fs); //路径压缩，压缩为一层
    }

    //合并两个集合
    void Union(T t1, T t2)
    {
        if (mp.find(t1) == mp.end() || mp.find(t2) == mp.end())
        {
            return;
        }
        int fa1 = Findroot(t1);
        int fa2 = Findroot(t2);
        if (fa1 != fa2)
        {
            _fa[fa1] += _fa[fa2];
            _fa[fa2] = fa1;
        }
    }

    //统计并查集中一个有多少个集合
    size_t count()
    {
        int cnt = 0;
        for (auto i : _fa)
        {
            if (i < 0)
            {
                cnt++;
            }
        }
        return cnt;
    }


    //判断是否为一个集合
	bool InSet(const V& v1, const V&v2)
	{
		return FindRoot(v1) == FindRoot(v2);
	}
private:
    unordered_map<T, int> mp;  //存放内容和下标的对应关系
    unordered_map<int, T> mpt; //存放下标和存放内容的对应关系
    vector<int> _fa;           //存放父亲下标的数组
};
